Modern digital packet communication networks commonly employ a connection-oriented protocol such as the widely-used Transmission Control Protocol/Internet Protocol (TCP/IP) suite to assure reliable inter-process communication between pairs of processes in host computers. The TCP is described by Postel in RFC 793 of the U.S. Defense Advanced Research Projects Agency (DARPA), entitled “Transmission Control Protocol: DARPA Internet Program Protocol Specification” (1981), which is incorporated herein by reference. “Connection-oriented” signifies that a pair of processes wishing to exchange messages must execute a procedure to establish a connection between them (e.g., the three-way handshake defined for the TCP in RFC 793), and that any messages sent are associated with the connection. Thus, a connection is a unique logical link between two processes attached to a networks established by mutual consent, allowing an exchange of messages between the processes, and terminated by one of the two processes upon conclusion of the exchange. A single host computer can participate in a large number of connections, since a host can contain a plurality of processes, each of which may establish an independent connection.
A connection is characterized by a set of data termed a connection context, or a Transmission Control Block in RFC793 terms. The connection context comprises information such as the status of the connection, connection name, number of buffers awaiting acknowledgment, pointers to send and receive buffers, security data, and amount of time to allow before identifying a transmission timeout.
A process sending or receiving a packet requires access to the connection context in order to handle the packet correctly and efficiently. The process needs to retrieve information from the connection context, e.g., a pointer to a receive buffer, and must also modify the connection context, e.g., to increment the number of buffers awaiting acknowledgment. In order to minimize access time to connection context information, it would be desirable to store all connection contexts in a fast memory array, e.g., an on-chip memory. However, since the number of connections may be large, cost and size constraints generally preclude storing all connection contexts in such a fast memory.
A common strategy for balancing a need for fast access to frequently-used information with a need to access large amounts of information is caching. Caching makes use of a small fast memory cache to hold a portion of a total database, according to expectations about which data is likely to be accessed. When a process requests a data item, a caching mechanism first checks if the item already resides in the cache. If so, the data item is passed immediately to the requesting process. This situation is termed a “cache hit.” If the data item does not already reside in the cache, a situation termed a “cache miss” occurs, and the data item must be fetched from a main memory (a relatively slow operation), stored in the cache, and passed to the requesting process.
The expectations regarding which data is likely to be accessed rely on two properties of the access patterns of most programs: temporal locality, meaning that if an item is accessed once, it is likely to be accessed again soon; and spatial locality, signifying that if one memory location is accessed, nearby memory locations are also likely to be accessed. To track temporal locality, many cache management schemes entail an aging of the items in the cache in order to determine which items were accessed recently. In addition, spatial locality dictates that, when data is loaded into a cache, additional adjacent memory locations beyond the specific item requested are also loaded, in an attempt to anticipate future requests. As noted, a cache can usually hold only a portion of the entire database. When the cache is full and a cache miss has occurred, the cache management mechanism must replace an existing item of the cache with new data. A method of selecting which item to replace is termed a “replacement algorithm.” Least Recently Used (LRU) is one such replacement algorithm, based on temporal locality and calling for replacing items which were not accessed for the longest time. Another replacement algorithm known in the art calls for replacing a randomly-selected item in the cache.
Advances in network speed to multi-gigabit rates are driving developments to streamline and expedite all areas of network communications. Access to connection context information is one such area. Common cache replacement techniques, e.g., LRU and random replacement, while often suitable for the access patterns of a variety of general-purpose applications, do not necessarily provide adequate performance levels for network communications applications, particularly connection context caching.
Reference is now made to FIG. 1 which is a schematic block diagram illustrating a sample computer system using a Least Recently Used cache replacement algorithm on a connection context cache for four connections. Connections A, B, C, and D, also identified as 12, 14, 16, and 18 respectively, communicate with a network receiver 20, at the same rate but with a small phase shift. Arrivals of messages on connections A, B, C, and D constitute activating events for network receiver 20. A connection context cache 22 comprises a cache management mechanism, and can accommodate only two entries. FIG. 1 is a “snapshot” of connection C addressing receiver 20, and the effects on cache 22. Previous to the snapshot, receiver 20 received a first activating event (message arrival) from connection A (indicated by a dashed arrow 13 from Connection A to the receiver), causing a cache miss in a connection context cache 22. The cache management mechanism loaded a connection context A 26, from an external memory connection context database 24, thus making context A available to receiver 20. Shortly thereafter, connection B generated an activating event (indicated by a dashed arrow 15 from connection B to the receiver), resulting in another cache miss, and the loading of context B 28 from the external memory into the connection context cache (indicated by dashed arrows from contexts A and B in external memory 24, to contexts A and B in connection cache 22). Thus, the state of the connection context cache is as shown in FIG. 1, containing context data for connections A and B.
Connection C now generates a message to the receiver, an activating event indicated by a solid arrow 17 from connection C to the receiver. Since context C does not reside in the connection context cache, a cache miss occurs. The cache management mechanism must perform a “cache replacement,” i.e., replace one of the contexts with connection context C. Based on LRU, context A is replaced by context C: context A is stored back in the external memory in order to preserve modifications that occurred to conext A (indicated by a solid arrow from the connection context cache/context A to the external memory) and context C is fetched into the cache (indicated by a solid arrow from the external memory/context C to the connection context cache). After these actions, the connection context cache contains contexts B and C. The next event to occur is the arrival of a message via connection A, again resulting in a cache miss. The oldest context in the cache is now context B, which is replaced by fetching context A from external memory.
Table I presents the cache replacement pattern for the LRU cache system depicted in FIG. 1 and described in the foregoing:
TABLE IMessageCache contentsCycleArrivalafter arrivalCache miss?1AA[initial load]2BA B[initial load]3CB CYES4AA CYES5BA BYES6CB CYES
After initial loads in cycles 1 and 2, the cache miss rate is 100%. As is apparent from this simplified example, the connection context cache provides no performance benefit, since every access to a context results in a read operation from the slower external memory.
One attempt to address this shortcoming is disclosed in U.S. Pat. No. 5,761,716 to Byrn et al., whose disclosure is incorporated herein by reference. Byrn describes a method by which a cache entry is selected for replacement if it is a most recently used block among cache data blocks associated with a channel having a lowest data access rate. The cache replacement algorithm disclosed in the Byrn patent is termed “Lowest Rate, Most Recently Used.” The data access rate is equivalent to either a rate of data transfer in a system comprising data communication channels, or a priority associated with a task, in a case of a system comprising a plurality of tasks. The data access rates of the tasks or channels are considered cyclic, i.e., expressed in terms of a data access every N time slices. In addition, the data access rates are considered invariant over the life of the process or communication. The lowest rate, most recently used replacement algorithm provides some performance improvements over LRU.
As Byrn et al. describe, taking into account task priority can improve cache replacement performance. By the same token, understanding characteristics of network traffic may provide a way of improving cache systems for network applications. C. R. Baugh proposed a model for network traffic behavior in a paper titled “4IPP Traffic Model for IEEE 802.16.3,” submitted to the Institute for Electronic and Electrical Engineers (IEEE) Broadband Wireless Access Working Group, Session #10 on Oct. 31, 2000, which can be found at http://wirelessman.org/tg3/contrib/802163c-00—51. pdf, and which is incorporated herein by reference. Bauch suggests that a superposition of four Interrupted Poisson Processes (4IPP) has been proven to model self-similar traffic, i.e., network traffic in which there exists a high correlation between a present packet and a previous packet, such as is found in transmissions according to an Ethernet protocol and/or in the Internet. An IPP may be in one of two states: an ON state, when packets are generated; an OFF state, when packets are not generated. Further, an IPP is characterized by three parameters: transition probability rate C1, which is the number of transitions from the ON state to the OFF state per unit of time; transition probability rate C2, which is the number of transitions from the OFF state to the ON state per unit of time; and λ, the number of packets generated per unit of time when the process is in the ON state. Baugh states that “packet traffic is reasonably well modeled by using just 4 Interrupted Poisson Processes if the parameters of each Interrupted Poisson Process are appropriately chosen . . . . The 4IPP model superimposes 4 different time scales to generate an accurate representation of traffic for Ethernet and Internet.”